package _01_sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/22 - 23:48
 * 归并排序，自下而上，非递归实现
 */
public class MergeSortBottomUp2 {
    @Test
    public void test() {
        int[] arr = {2, 6, 4, 1, 8, 5, 9, 12, 75, 43, 56};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void mergeSort(int[] a1) {
        int n = a1.length;
        int[] a2 = new int[n];
        // width  代表有序区间的宽度
        for (int width = 1; width < n; width *= 2) {
            for (int left = 0; left < n; left += 2 * width) {
                // [left,right] 分别代表带合并区间的左右边界
                int right = Math.min(left + 2 * width - 1, n - 1);
//                System.out.printf("width %d [%d,%d]%n", width, left, right);
                int m = Math.min(left + width - 1, n - 1);
                merge(a1, left, m, m + 1, right, a2);
            }
            System.arraycopy(a2, 0, a1, 0, n);
        }
    }

    private void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
        int k = i;
        while (i <= iEnd && j <= jEnd) { // 表示两个区间都还有元素需要比较
            // 谁小就将谁添加到a2中，并且其指针+1
            if (a1[i] < a1[j]) {
                a2[k] = a1[i++];
            } else {
                a2[k] = a1[j++];
            }
            k++;
        }
        if (i > iEnd) {
            // 如果i范围的元素比较完了，那么j范围的剩余元素全部追加到a2末尾
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
        }
        if (j > jEnd) {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
        }
    }
}
